/* 

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

var mergeTwoLists = function (l1, l2) {
    if (l1 === null) return l2;
    if (l2 === null) return l1;

    let dummyHead = p = new ListNode();

    while (l1 !== null && l2 !== null) {
        if (l1.val > l2.val) {
            p.next = l2;
            l2 = l2.next;
            p = p.next;
        } else {
            p.next = l1;
            l1 = l1.next;
            p = p.next;
        }
    }

    p.next = l1 ? l1 : l2;

    return dummyHead.next;
};

// 自底向上归并排序
var sortList = function (head) {
    if (head === null) {
        return head;
    }
    let length = 0;
    let node = head;
    while (node !== null) {
        length++;
        node = node.next;
    }
    let dummyHead = new ListNode(0, head);
    // "subLength <<= 1" 是 "subLength = (subLength << 1)"
    for (let subLength = 1; subLength < length; subLength <<= 1) {
        let prev = dummyHead,
            curr = dummyHead.next;
        while (curr !== null) {
            let head1 = curr;
            for (let i = 1; i < subLength && curr.next !== null; i++) {
                curr = curr.next;
            }
            let head2 = curr.next;
            curr.next = null;
            curr = head2;
            for (let i = 1; i < subLength && curr != null && curr.next !== null; i++) {
                curr = curr.next;
            }
            let next = null;
            if (curr !== null) {
                next = curr.next;
                curr.next = null;
            }
            let merged = mergeTwoLists(head1, head2);
            prev.next = merged;
            while (prev.next !== null) {
                prev = prev.next;
            }
            curr = next;
        }
    }
    return dummyHead.next;
};